package bch.maven.plugin.guava.business;

import cn.hutool.core.lang.Pair;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class MuskCyclePrinter {

    public static void main(String[] args) {
        Map<Long, Pair<Long, Long>> parentMap = Map.of(
                28L, Pair.of(31L, null),
                29L, Pair.of(28L, null),
                30L, Pair.of(28L, null),
                31L, Pair.of(29L, 30L)
        );

        printCycle(31L, parentMap);
        printCycle(30L, Map.of(30L, Pair.of(31L, null)));
        printCycle(30L, Map.of(30L, Pair.of(31L, 32L)));
        printCycle(30L, Map.of(30L, Pair.of(31L, 32L)
                , 31L, Pair.of(33L, 34L)
                , 32L, Pair.of(35L, 36L)))
        ;
    }

    public static void printCycle(Long currentId, Map<Long, Pair<Long, Long>> parentMap) {
        // 路径
        List<Long> path = new ArrayList<>();
        path.add(currentId);
        List<List<Long>> allCycles = new ArrayList<>();

        Pair<Long, Long> parents = parentMap.get(currentId);
        if (parents != null) {
            if (parents.getKey() != null) {
                dfs(parents.getKey(), parentMap, path, allCycles);
            }
            if (parents.getValue() != null) {
                dfs(parents.getValue(), parentMap, path, allCycles);
            }
        }

        // 打印所有环路
        if (allCycles.isEmpty()) {
            System.out.println("未发现环路");
        } else {
            for (List<Long> cycle : allCycles) {
                System.out.println("发现环路: " + String.join(" -> ", cycle.stream().map(String::valueOf).toList()));
            }
        }
    }

    private static void dfs(Long node,
                            Map<Long, Pair<Long, Long>> parentMap,
                            List<Long> path,
                            List<List<Long>> cycles) {

        if (path.contains(node)) {
            // 构建闭环路径
            int idx = path.indexOf(node);
            List<Long> cycle = new ArrayList<>(path.subList(idx, path.size()));
            // 闭环
            cycle.add(node);
            cycles.add(cycle);
            return;
        }

        path.add(node);

        Pair<Long, Long> parents = parentMap.get(node);
        if (parents != null) {
            Long[] nexts = {parents.getKey(), parents.getValue()};
            for (Long parent : nexts) {
                if (parent != null) {
                    dfs(parent, parentMap, path, cycles);
                }
            }
        }

        path.removeLast();
    }

}
